package com.suanfa;

public class Test07 {
    // 主函数测试
    public static void main(String[] args) {
        int[] sortedArray = {10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100};
        int target = 85;

        int index = fibonacciSearch(sortedArray, target);
        if (index != -1) {
            System.out.println("目标值 " + target + " 在数组中的索引为: " + index);
        } else {
            System.out.println("未找到目标值 " + target);
        }
    }

    // 查找目标值的位置
    public static int fibonacciSearch(int[] arr, int target) {
        int max = arr.length;

        // 初始化斐波那契数列
        int fibM2 = 0; // F(k-2)
        int fibM1 = 1; // F(k-1)
        int fibMk = fibM2 + fibM1; // F(k)

        // 找到一个大于等于数组长度的斐波那契数
        while (fibMk < max) {
            fibM2 = fibM1;
            fibM1 = fibMk;
            fibMk = fibM2 + fibM1;
        }

        // 假设arr[fibMk]可以扩展数组至fibMk长度
        // low是起始索引
        int offset = -1;

        while (fibMk > 1) {
            // 确保i不超过数组边界
            int i = Math.min(offset + fibM2, max - 1);

            if (arr[i] < target) {
                // 目标在右侧
                fibMk = fibM1;
                fibM1 = fibM2;
                fibM2 = fibMk - fibM1;
                offset = i;
            } else if (arr[i] > target) {
                // 目标在左侧
                fibMk = fibM2;
                fibM1 = fibM1 - fibM2;
                fibM2 = fibMk - fibM1;
            } else {
                // 找到了
                return i;
            }
        }

        // 最后检查是否为第一个元素
        if (fibM1 == 1 && arr[offset + 1] == target) {
            return offset + 1;
        }

        // 没有找到
        return -1;
    }


}